package com.ly.algorithm.leetcode.dp;

import java.util.Arrays;

/**
 * @Classname Problem416
 * @Description
 * 给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。
 *
 * 注意:
 *
 * 每个数组中的元素不会超过 100
 * 数组的大小不会超过 200
 * 示例 1.txt:
 *
 * 输入: [1, 5, 11, 5]
 *
 * 输出: true
 *
 * 解释: 数组可以分割成 [1.txt, 5, 5] 和 [11].
 *  
 *
 * 示例 2:
 *
 * 输入: [1.txt, 2, 3, 5]
 *
 * 输出: false
 *
 * 解释: 数组不能分割成两个元素和相等的子集.
 * @Date 2020/10/11 19:04
 * @Author 冷心影翼
 */
public class Problem416 {

	public static void main(String[] args) {
		Solution416 solution416 = new Solution416();
		System.out.println(solution416.canPartition(new int[]{1, 2, 3, 5}));
		System.out.println(solution416.canPartitionDP2(new int[]{1, 5,11,5,3,3}));

	}
}


class Solution416 {
	public boolean canPartition(int[] nums) {
		int sum = Arrays.stream(nums).sum();
		if(sum % 2 != 0)
			return false;

		sum = sum >> 1;
		return canPartition(nums,nums.length-1,sum);
	}

	public boolean canPartitionDP2(int[] nums) {
		int sum = 0;
		for (int num : nums) sum += num;

		if (sum % 2 != 0) return false;

		int target = sum / 2;
		boolean[][] dp = new boolean[nums.length+1][target+1];

		for (int i = 0; i < nums.length + 1; i++) {
			dp[i][0] = true;
		}
		for (int i = 1; i < nums.length + 1; i++) {
			for (int j = 1; j < target + 1; j++) {
				if(nums[i-1] <= j) {
					dp[i][j] = dp[i-1][j-nums[i-1]] || dp[i-1][j];
				}else {
					dp[i][j] = dp[i-1][j];
				}
			}
		}
		return dp[nums.length][target];
	}

		public boolean canPartitionDP1(int[] nums) {
			int sum = 0;
			for (int num : nums) sum += num;

			if ((sum & 1) == 1) return false;

			int target = sum / 2;
			boolean[] dp = new boolean[target + 1];
			dp[0] = true;

			for (int num : nums)
				for (int i = target; i >= num; i--)
					dp[i] = dp[i] || dp[i - num];

			return dp[target];
		}


	public boolean canPartition(int[] nums,int n,int sum) {
		if(n == 0) {
			if(nums[0] == sum) {
				return true;
			}
			return false;
		}else {
			if(nums[n]>sum) {
				return canPartition(nums,n-1,sum);
			}else if(nums[n] == sum) {
				return true;
			}else {
				return canPartition(nums,n-1,sum-nums[n]) || canPartition(nums,n-1,sum);
			}
		}
	}

}